The present invention relates generally to computer data storage systems and more particularly to systems for reconfiguration of data storage.
Computer data systems today are huge and complex. Examples are: data related banking records, the internet, data mining systems, libraries, and scientific applications like planning for weather forecasting. All of this data is now being stored on-line so that the data can be manipulated.
One major problem is efficient access to this stored data. An analogy would be data storage as a library, with the data as the books in the library, and the data storage devices as shelves for the books. Different data storage devices hold different blocks of data, just as in a library where different shelves hold different books. It is desired that data be arranged on storage devices, as books are arranged on shelves, for the most efficient access.
From a library perspective, it is most efficient for storage of all of the most frequently read books to be stored on one shelf. However, this is not the most efficient from a user perspective because all the users would be trying to access that one shelf. The same is true for data storage. If all of the most frequently used data is on one data storage device, it creates a bottleneck on the data storage device because it is possible to retrieve only a certain amount of data from a data storage device per unit of time. Thus, a way to configure data storage to optimize throughput of the data storage system is necessary.
However, it is difficult to determine optimum data storage system configurations. It is necessary to look at workload patterns, how data is accessed, and what is important to the user. There are thousands, if not millions of blocks of data which must be considered.
There are individuals employed in many companies who regularly reconfigure the data storage in the data storage systems, and this is currently all being done manually. At the present time, the experts try and partition the problem into easy pieces. The people who do this are highly skilled and rely primarily on past experience, but there is no formalism to the reconfiguration process. Thus, a long sought, but unattained, objective in the field of data storage is to formalize the process and to make it easy, quantifiable, and quick to optimize a data storage system.
However, even if it were possible to optimize each storage system, even automatically, the problem is that workloads change. Over time, the most frequently used data changes. There are different blocks of data in the storage system. The access patterns to these blocks of data changes over time. Further, devices may fail or be added or subtracted. Thus, the ultimate goal is a data storage system which is not only able to automatically configure itself, but to reconfigure itself xe2x80x98on-the-flyxe2x80x99; i.e. move stored data around based on changing access patterns.
Currently, it is necessary to take the whole data storage system down off-line, reconfigure it, and then bring it back up. This is an increasing problem because customers cannot really afford to take their systems down at all. For example, a bank needs to have its automated teller machine systems available twenty-four hours a day, seven days a week, fifty-two weeks a year.
In the past, it has been a major set of goals to automatically optimize data storage configurations, change data storage configurations during data system operation, and to minimize the time that it takes to reconfigure the data storage system.
The present invention provides a computer data storage system with a migration plan generator which includes a xe2x80x9cSimplexe2x80x9d migration planner which provides for making terminal moves until no further terminal moves are possible based on random, preset, or functional ordering. A terminal move is a move of data to a data storage device where it belongs in a goal configuration. The moves make up a migration plan which is further processed to parallelize moves where possible to speed up the migration plan.
The present invention further provides a computer data storage system with migration plan generator which includes a xe2x80x9cSimplexe2x80x9d migration planner which provides for making terminal moves until no further terminal moves are possible, then making xe2x80x9cshuntxe2x80x9d moves, or non-terminal moves, until further terminal moves can be made. The moves make up a migration plan which is further processed to parallelize moves where possible to speed up the migration plan.
The present invention further provides a computer data storage system with a migration plan generator which includes a xe2x80x9cGreedyxe2x80x9d migration planner which uses a xe2x80x9ccontentionxe2x80x9d metric. The xe2x80x9ccontentionxe2x80x9d of a data storage device is defined as the total size of the data stores that need to move onto such data storage device, divided by the amount of free space on such data storage device. The contention of the entire system is the sum of the contention over all the data storage devices. The migration plan generator develops a plan that leads to the lowest contention for the system.
The present invention further provides a computer data storage system with a migration plan generator which includes a xe2x80x9cCyclexe2x80x9d migration planner which finds shunts by first trying to find cycles with small data stores in a Greedy fashion. Once the smallest data store is moved off a data storage device, the largest data store in the cycle is shunted to any data storage device that can accommodate it.
The present invention further provides a computer data storage system with a migration plan generator which includes a xe2x80x9cHillclimbingxe2x80x9d migration planner which uses a global contention metric which seeks the closest local minimum for the contention metric.
The present invention further provides a computer data storage system with a migration plan generator which includes a xe2x80x9cSimulated Annealingxe2x80x9d migration planner which uses a probabilistic Hilldlimbing approach that will sometimes choose moves that do not improve the optimization metric.
The present invention further provides a computer data storage system with a migration plan generator which includes a xe2x80x9cMetaxe2x80x9d migration planner which shifts from one planner to another based on the planner""s performance.